#include<stdio.h>
#include<string.h>
#include"big_int.h"
#include"rand-dev.h"
#define BITS 1024

int is_prime(big_unsigned *num){
	static const uint32_t basic_prime[]={2,3,5,7,11,13,17,19,23,29};
	big_unsigned two=big_unsigned_from_unsigned(2);
	int cmp=big_unsigned_cmp(num,&two);
	if(cmp==0)
		return 1;
	if(cmp<0 || !big_unsigned_is_odd(num))
		return 0;
	big_unsigned num_minus1=big_unsigned_copy(num);
	big_unsigned_decline(&num_minus1);
	big_unsigned base=big_unsigned_copy(&num_minus1);
	size_t index=big_unsigned_lowbit(&base);
	big_unsigned_rshift(&base,index);
	big_unsigned one=big_unsigned_from_unsigned(1);
	int result=1;
	for(int i=0;i<sizeof(basic_prime)/sizeof(uint32_t) && (num->size>1 || (num->size && num->num[0]>basic_prime[i]));i++){
		big_unsigned tmp=big_unsigned_mod_power(basic_prime[i],&base,num);
		if(big_unsigned_cmp(&tmp,&one)==0 || big_unsigned_cmp(&tmp,&num_minus1)==0)
			continue;
		size_t j;
		for(j=0;j<index;j++){
			big_unsigned_mod_multiply(&tmp,&tmp,num);
			if(big_unsigned_cmp(&tmp,&num_minus1)==0)
				break;
			if(big_unsigned_cmp(&tmp,&one)==0){
				j=index;
				break;
			}
		}
		big_unsigned_destruct(&tmp);
		if(j==index){
			result=0;
			break;
		}
	}
	big_unsigned_destruct(&one);
	big_unsigned_destruct(&base);
	big_unsigned_destruct(&num_minus1);
	big_unsigned_destruct(&two);
	return result;
}
void rand_prime(){
	rand_dev rd;
	rand_dev_construct(&rd);
	int cont=1;
	while(cont){
		big_unsigned num=big_unsigned_rand(&rd,BITS>>3); // BITS/8
		if(is_prime(&num)){
			big_unsigned_print(&num);
			putchar('\n');
			cont=0;
		}
		big_unsigned_destruct(&num);
	}
	rand_dev_destruct(&rd);
}
void determine_prime(){
	char buf[309+2];
	getchar();
	while(1){
		printf("enter the number ('exit' to exit): ");
		fgets(buf,sizeof(buf),stdin);
		if(strcmp(buf,"exit\n")==0)
			return;
		big_unsigned num=big_unsigned_from_string(buf);
		puts(is_prime(&num)?"Yes":"No");
		big_unsigned_destruct(&num);
	}
}
int main(){
	printf("1. rand a prime\n2. determine the prime\n0. exit\n> ");
	input:
	switch(getchar()){
		case '1':
			rand_prime();
			break;
		case '2':
			determine_prime();
			break;
		case '0':
			break;
		default:
			goto input;
	}
	return 0;
}